3.13.3. Основные принципы помехоустойчивого кодирования.

         Кодирование с исправлением ошибок, по существу, представляет собой метод обработки сигналов, предназначенный для увеличения надежности передачи по цифровым каналам. Хотя различные схемы кодирования очень непохожи друг на друга и основаны на различных математических теориях, всем им присущи два общих свойства. Одно из них - использование избыточности. Закодированные цифровые сообщения всегда содержат дополнительные, или избыточные, символы. Эти символы используют для того, чтобы подчеркнуть индивидуальность каждого сообщения. Их всегда выбирают так, чтобы сделать маловероятной потерю сообщением его индивидуальности из-за искажения при воздействии помех достаточно большого числа символов. Второе свойство состоит в усреднении шума. Эффект усреднения достигается за счет того, что избыточные символы зависят от нескольких информационных символов. Для понимания процесса кодирования полезно рассмотреть каждое из этих свойств отдельно.
         Рассмотрим вначале двоичный канал связи с помехами, приводящими к тому, что ошибки появляются независимо в каждом символе и средняя вероятность ошибки равна Р = 0,01. Если требуется рассмотреть произвольный блок из 10 символов на выходе канала, то весьма трудно выявить символы, которые являются ошибочными. Вместе с тем если считать, что такой блок содержит не более трех ошибок, то решение будет ошибочным лишь два раза на миллион блоков. Кроме того, вероятность правильного решения возрастает с увеличением длины блока. При увеличении длины блока доля ошибочных символов в блоке стремится к средней частоте ошибок в канале, а также, что очень важно, доля блоков, число ошибок в которых существенно отличается от этого среднего значения, становится очень малой. Для подтверждения этого утверждения, вычислим вероятность того, что доля ошибочных символов превышает значение р, и построим график этой функции для нескольких значений длины блока (рис.3.23).


Рис. 3.23. Вероятность того, что доля ошибочных символов e/N в блоке длиной N
превышает p при вероятности Pe = 0,01.

         Как видно из рисунка, при обработке символов блоками, а не одного за другим, можно уменьшить общую частоту ошибок, при условии, что существует схема кодирования нечувствительная к ошибкам в некоторой доле символов блока и не приводящая при этом к потере информации, т. е. не формирующий ошибочный блок. Из графиков на рис.3.22 для различных длин блоков видно, какую именно долю ошибок нужно исправлять, чтобы получить заданную вероятность ошибки блока. Также видно, что при фиксированной вероятности ошибки блока доля ошибок, которые нужно исправлять, уменьшается при возрастании длины блока, т.е. существуют резервы улучшения характеристик при усреднении шума и о том, что эти резервы возрастают при увеличении длины блока. Таким образом, длинные блоковые коды эффективнее коротких.
        Показанную целесообразность исправления ошибок в символах, можно реализовать на основе избыточности. При исправлении ошибок в сообщении, представляемом последовательностью из n двоичных символов, очень важно учесть, что не каждая из двух возможных последовательностей представляет истинное сообщения. Действительно, любая из возможных принятых последовательностей из n символов может представлять истинное сообщение и нет никаких оснований считать, что одна из них является более истинной, чем другая. Продолжая рассуждать таким же способом, можно видеть, что для исправления всех наборов из t или менее ошибок необходимо и достаточно, чтобы каждая последовательность, представляющая сообщение, отличалась от последовательности, представляющее любое другое сообщение, не менее чем в 2t + l местах. Например, для исправления всех одиночных или всех двойных ошибок в символах нужно, чтобы каждые две последовательности, представляющие разные сообщения, отличались не менее чем в пяти символах. Каждая принятая последовательность, содержащая два ошибочных символа и, следовательно, отличающаяся от посланной последовательности ровно в двух местах, будет всегда отличаться от всех других последовательностей, представляющих сообщения, не менее чем в трех местах. Число позиций, в которых две последовательности отличаются друг от друга, называют расстоянием Хемминга и обозначают через d. Наименьшее значение d для всех пар кодовых последовательностей называется кодовым расстоянием и обозначается dmin. Поскольку dmin всегда должно быть на единицу больше удвоенного числа исправляемых ошибок, можно записать

        Параметр t указывает, что все комбинации из t или менее ошибок в любой принятой последовательности могут быть исправлены. Существуют модели каналов, в которых значение t может быть больше чем указанно в (3.4.).Например, рассмотрим код состоящий из четырех кодовых слов 00000, 00111,11100 и 11011. Каждое кодовое слово используется для представления одного из четырех возможных сообщений. Поскольку код включает лишь небольшую долю всех 32 возможных последовательностей из пяти символов, мы можем выбрать кодовые слова таким образом, чтобы каждые два из них отличались друг от друга не менее чем в трех позициях. Таким образом, кодовое расстояние равно трем и код может исправлять одиночную ошибку в любой позиции.
         При декодирования такого кода, каждой из 28 недопустимых последовательностей нужно поставить в соответствие ближайшую к ней допустимую последовательность. Этот процесс ведет к созданию таблицы декодирования, которая строится следующим образом. Вначале под каждым кодовым словом выписываем все возможные последовательности, отличающиеся от него в одной позиции. В результате получают часть в таблице 3.2, заключенную между штриховыми линиями. Оставшиеся после такого построения восемь последовательностей отличаются не менее чем в двух позициях Однако в отличие от других последовательностей эти восемь последовательностей нельзя однозначно разместить в таблице. При использовании данной таблицы в процессе декодирования нужно найти столбец, в котором содержится принятая последовательность, а в качестве выходной последовательности декодера взять кодовое слово, находящееся в верхней строке этого столбца.

        Причина, по которой таблица декодирования должна строиться именно таким образом, очень проста. Вероятность появления фиксированной комбинации из i ошибок равна . Заметим, что при
        Таким образом, появление фиксированной одиночной ошибки более вероятно, чем фиксированной комбинации двух ошибок, и т. д. Это означает, что декодер, который декодирует каждую принятую последовательность в ближайшее к ней по расстоянию Хемминга кодовое слово, выбирает в действительности то кодовое слово, вероятность передачи которого максимальна (в предположении, что все кодовые слова равновероятны). Декодер, реализующий это правило декодирования, является декодером максимального правдоподобия, и в указанных предположениях он минимизирует вероятность появления ошибки декодирования принятой последовательности. В этом смысле такой декодер является оптимальным. Это понятие очень важно, поскольку декодеры максимального правдоподобия часто используются для коротких кодов. Кроме того, параметры декодера максимального правдоподобия могут служить эталоном, с которым сравниваются параметры других, неоптимальных декодеров. Если декодирование ведется с помощью таблицы декодирования, то элементы таблицы можно расположить так, чтобы получить декодирование по максимуму правдоподобия. К сожалению, объем таблицы растет экспоненциально с ростом длины блока, так что использование таблицы декодирования для длинных кодов нецелесообразно. Однако таблица декодирования часто оказывается полезной для выяснения важных свойств блоковых кодов.
        Множество кодовых слов в таблице декодирования является подмножеством (первой строкой таблицы декодирования) множества всех 2" последовательностей длиной n. В процессе построения таблицы декодирования множество всех последовательностей длиной n разбивается на непересекающиеся подмножества (столбцы таблицы декодирования). В случае, когда код исправляет t ошибок, число Ne последовательностей длиной n в каждом подмножестве удовлетворяет неравенству

        Неравенство (3.5) следует непосредственно из того, что имеется ровно n различных последовательностей, отличающихся от данной последовательности в одной позиции. Сn2 - последовательностей, отличающихся в двух позициях, и т. д. Как и в приведенном выше простом примере, после размещения всех последовательностей, отличающихся от кодовых в t или менее позициях, почти всегда остаются неразмещенные последовательности (отсюда неравенство в (3.5)). Теперь можно связать избыточность кода с числом ошибок, которые им исправляются. Заметим сначала, что число всех возможных последовательностей равно 2n Каждый столбец таблицы декодирования содержит Nc таких последовательностей, поэтому общее число кодовых слов должно удовлетворять неравенству

        Это неравенство называется границей Хемминга или границей сферической упаковки. Равенство в (3.6) достигается только для так называемых совершенных кодов. Эти коды исправляют все наборы из t или менее ошибок и не исправляют никаких других наборов. Число известных совершенных кодов очень невелико, так что равенство в (3.6) достигается в очень редких случаях.
        Процесс кодирования состоит в том, что наборы k информационных символов отображаются в кодовые последовательности, состоящие из n символов. Любое такое отображение будем называть (n,k)-кодом, хотя обычно такое название применяется только к линейным кодам. Поскольку число последовательностей длиной k равно 2к, неравенство (3.6) можно переписать следующим образом

Мера эффективности кода определяется отношением

и называется скоростью кода. Доля избыточно передаваемых символов равна 1-R. Отображение, возникающее при кодировании, можно задавать таблицей кодирования. Например, код с четырьмя кодовыми словами имеет вид


        Часть кодовой последовательности, заключенная между штриховыми линиями, совпадает с входной последовательностью. Поэтому каждой кодовой последовательности, легко однозначно сопоставить входную последовательность. Не все блоковые коды обладают этим свойством. Коды обладающими такими свойствами называются систематическими кодами. Для систематических кодов, приведенных в таблице 3.2, избыточными являются символы на позициях 1, 4 и 5. Коды, не обладающие указанным свойством, называются несистематическими.
        Существует много относительно простых методов кодирования, позволяющих исправлять кратные ошибки и приводящих к заметному уменьшению частоты появления ошибочных символов. Такие коды строятся на базе современных полупроводниковых устройств и относительно просто декодируются. Например, существует блоковый код длиной 40, содержащий 50% избыточных символов и позволяющий исправлять четыре случайные ошибки. На рис.3.23 показано, что при Ре=0,01 этот код имеет вероятность ошибки блока, меньшую 10"4. Если этого недостаточно, можно либо увеличить избыточность, чтобы исправлять большее число ошибок, либо перейти к кодам с большей длиной блока и получить выигрыш за счет большего усреднения. В каждом случае нужно принимать во внимание возникающие дополнительные затраты. Однако обе указанные возможности допустимы и могут представлять практически приемлемые альтернативы.
         В заключении отметим, что форма кривых, изображенных на рис.3.23, позволяет предположить, что если имеется схема, исправляющая фиксированную долю t/n ошибочных символов в блоке (в нашем случае t/n незначительно превышает 0,01), то, выбирая длину блока достаточно большой, можно сделать долю ошибок сколь угодно малой. К сожалению, это оказывается очень трудной задачей. Большинство схемных решений может обеспечить постоянное отношение t/n лишь при возрастающей доле избыточных символов. Таким образом, потеря эффективности возникает из-за того, что доля полезных сообщений становится очень малой при большой длине блока. Частично эта задача была решена Юстесеном в 1972 г. Он показал, что можно построить класс асимптотически хороших (в указанном здесь смысле) кодов и указать для них процедуру декодирования. Однако, насколько известно, эти коды не применялись ни в одной из существующих систем связи.